package _08_DFS;

public class _85_最大矩形 {

    public static void main(String[] args) {

        _85_最大矩形 v = new _85_最大矩形();


        char[][] chars = {
            {'1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '1', '1', '1', '1', '1', '1', '0'},
            {'1', '1', '1', '1', '1', '1', '1', '0'},
        };
        System.out.println(v.maximalRectangle(chars));

    }

    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) return 0;
        int col = matrix[0].length;
        int max = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == '1') {
                    int tempRow = i;
                    int tempCol = j;
                    // 高度延展
                    while (tempRow < row - 1 && matrix[tempRow + 1][j] == '1')
                        tempRow++;
                    while (tempCol < col - 1 && matrix[i][tempCol + 1] == '1')
                        tempCol++;
                    for (int k = i; k <= tempRow; ++k) {
                        for (int l = j; l <= tempCol; ++l) {
                            if (matrix[k][l] == '1') {
                                max = Math.max((k - i + 1) * (l - j + 1), max);
                            } else {
                                tempCol = l - 1;
                                break;
                            }
                        }
                    }
                }
            }
        }
        return max;
    }

}
